//前序遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) 
    {
        TreeNode* cur=root;
        vector<int> ret;
        stack<TreeNode*> st;
        //先访问左节点 再访问左节点的左子树  最后访问左节点的右子树
        while(cur||!st.empty())
        {
            //访问左子树
            while(cur)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur=cur->left;
            }

            //转化为右子树的访问
            TreeNode* t=st.top();
            st.pop();
            cur=t->right;
        }

        return ret;
        
    }
};

//中序遍历
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root)
    {
        TreeNode* cur=root;
        stack<TreeNode*> st;
        vector<int> ret;

        //访问左路子树 访问左节点 再访问右路子树
        while(cur || !st.empty())
        {
            //访问左路子树
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }

            //访问左节点和右路子树
            TreeNode* t=st.top();
            st.pop();
            ret.push_back(t->val);
            cur=t->right;
        }

        return ret;
        
    }
};
//后序遍历
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) 
    {
        TreeNode* cur=root;
        stack<TreeNode*> st;
        vector<int> ret;
        TreeNode* prev=nullptr;

        while(cur || !st.empty())
        {
            //左节点及左路节点入栈
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }

            TreeNode* t=st.top();
            //判断是否访问的为根节点：右子树为空 || 右子树已经被访问过
            if(t->right==nullptr || t->right==prev)
            {
                ret.push_back(t->val);
                prev=t;
                st.pop();
            }
            else
            {
                cur=t->right;
            }
        }
        return ret;
    }
};